{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Ones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumNumberOfOnes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中 1 的最大数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现在有一个尺寸为 <code>width * height</code>&nbsp;的矩阵&nbsp;<code>M</code>，矩阵中的每个单元格的值不是&nbsp;<code>0</code>&nbsp;就是&nbsp;<code>1</code>。</p>\n",
    "\n",
    "<p>而且矩阵 <code>M</code> 中每个大小为&nbsp;<code>sideLength * sideLength</code>&nbsp;的 <strong>正方形</strong> 子阵中，<code>1</code> 的数量不得超过&nbsp;<code>maxOnes</code>。</p>\n",
    "\n",
    "<p>请你设计一个算法，计算矩阵中最多可以有多少个 <code>1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>width = 3, height = 3, sideLength = 2, maxOnes = 1\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "题目要求：在一个 3*3 的矩阵中，每一个 2*2 的子阵中的 1 的数目不超过 1 个。\n",
    "最好的解决方案中，矩阵 M 里最多可以有 4 个 1，如下所示：\n",
    "[1,0,1]\n",
    "[0,0,0]\n",
    "[1,0,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>width = 3, height = 3, sideLength = 2, maxOnes = 2\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "[1,0,1]\n",
    "[1,0,1]\n",
    "[1,0,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= width, height &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= sideLength &lt;= width, height</code></li>\n",
    "\t<li><code>0 &lt;= maxOnes &lt;= sideLength * sideLength</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-ones](https://leetcode.cn/problems/maximum-number-of-ones/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-ones](https://leetcode.cn/problems/maximum-number-of-ones/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n3\\n2\\n1', '3\\n3\\n2\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        w0, w1 = width // sideLength, width % sideLength\n",
    "        h0, h1 = height // sideLength, height % sideLength\n",
    "        \n",
    "        if maxOnes <= w1 * h1:\n",
    "            return maxOnes * (w0 + 1) * (h0 + 1)\n",
    "        \n",
    "        res = w1 * h1 * (w0 + 1) * (h0 + 1)\n",
    "        maxOnes -= w1 * h1\n",
    "        \n",
    "        loc1, cnt1 = (sideLength - w1) * h1, w0 * (h0 + 1)\n",
    "        loc2, cnt2 = (sideLength - h1) * w1, h0 * (w0 + 1)\n",
    "        if cnt1 < cnt2:\n",
    "            loc1, loc2 = loc2, loc1\n",
    "            cnt1, cnt2 = cnt2, cnt1\n",
    "        \n",
    "        if maxOnes <= loc1 + loc2:\n",
    "            if maxOnes <= loc1:\n",
    "                return res + maxOnes * cnt1\n",
    "            else:\n",
    "                return res + loc1 * cnt1 + (maxOnes - loc1) * cnt2\n",
    "        else:\n",
    "            return res + loc1 * cnt1 + loc2 * cnt2 + (maxOnes - loc1 - loc2) * w0 * h0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        res = 0\n",
    "        w0, w1 = width // sideLength, width % sideLength\n",
    "        h0, h1 = height // sideLength, height % sideLength\n",
    "        if maxOnes <= w1 * h1:\n",
    "            return maxOnes * (w0 + 1) * (h0 + 1)\n",
    "        res += w1 * h1 * (w0 + 1) * (h0 + 1)\n",
    "        maxOnes -= w1 * h1\n",
    "        loc1, cnt1 = (sideLength - w1) * h1, w0 * (h0 + 1)\n",
    "        loc2, cnt2 = (sideLength - h1) * w1, (w0 + 1) * h0\n",
    "        if maxOnes <= loc1 + loc2:\n",
    "            if cnt1 > cnt2:\n",
    "                if maxOnes <= loc1:\n",
    "                    return res + maxOnes * cnt1\n",
    "                else:\n",
    "                    return res + loc1 * cnt1 + (maxOnes - loc1) * cnt2\n",
    "            else:\n",
    "                if maxOnes <= loc2:\n",
    "                    return res + maxOnes * cnt2\n",
    "                else:\n",
    "                    return res + loc2 * cnt2 + (maxOnes - loc2) * cnt1\n",
    "        else:\n",
    "            res += loc1 * cnt1 + loc2 * cnt2\n",
    "            maxOnes -= (loc1 + loc2)\n",
    "            return res + maxOnes * w0 * h0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        cnt = []\n",
    "        for i in range(sideLength):\n",
    "            for j in range(sideLength):\n",
    "                hh = (height -i -1)//sideLength + 1\n",
    "                ww = (width-j - 1)//sideLength + 1\n",
    "                cnt.append(hh*ww)\n",
    "        cnt.sort(reverse = True)\n",
    "        return sum(cnt[:maxOnes])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        a = []\n",
    "        wq, wr = divmod(width, sideLength)\n",
    "        hq, hr = divmod(height, sideLength)\n",
    "        for r in range(sideLength):\n",
    "            for c in range(sideLength):\n",
    "                ww = wq + 1 if r < wr else wq\n",
    "                hh = hq + 1 if c < hr else hq\n",
    "                a.append(ww * hh)\n",
    "        a.sort(reverse = True)\n",
    "        return sum(a[:maxOnes])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        a = []\n",
    "        wq, wr = divmod(width, sideLength)\n",
    "        hq, hr = divmod(height, sideLength)\n",
    "        for r in range(sideLength):\n",
    "            for c in range(sideLength):\n",
    "                ww = wq + 1 if r < wr else wq \n",
    "                hh = hq + 1 if c < hr else hq \n",
    "                a.append(ww * hh)\n",
    "        a.sort(reverse=True)\n",
    "        return sum(a[:maxOnes\n",
    "        ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        res = []\n",
    "        wq, wr = divmod(width, sideLength)\n",
    "        hq, hr = divmod(height, sideLength)\n",
    "        for i in range(sideLength):\n",
    "            for j in range(sideLength):\n",
    "                ww = wq + 1 if i < wr else wq \n",
    "                hh = hq + 1 if j < hr else hq\n",
    "                res.append(ww * hh)\n",
    "        res.sort(reverse = True)\n",
    "        return sum(res[:maxOnes])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "整体思路：\n",
    "1）各个sideLength正方形从左上角紧凑排列，则只要每个正方形内1的布局完全一致，则无论如何移动矩形其内1的数量必定也一致（由于各正方形布局完全一致，移动过程中左边少一个右边必然多一个，上下亦然）\n",
    "2）只需把maxOnes先往等效区域多的格子上分配，则整个大区域1的数量必然最多且正方形内只有maxOnes个1\n",
    "'''\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        # 根据除以sideLength的余数，将每个sideLength正方形切割成四个部分（左上部分长宽等于2个余数）\n",
    "        w0, w1 = width // sideLength, width % sideLength\n",
    "        h0, h1 = height // sideLength, height % sideLength\n",
    "        \n",
    "        # 左上部分的等效区域为(w0 + 1) * (h0 + 1)个\n",
    "        if maxOnes <= w1 * h1:\n",
    "            return maxOnes * (w0 + 1) * (h0 + 1)\n",
    "        \n",
    "        # 分块处理：左上区域填满，余下的往右上和左下两个区域中等效个数多的区域分配\n",
    "        res = w1 * h1 * (w0 + 1) * (h0 + 1)\n",
    "        maxOnes -= w1 * h1\n",
    "        \n",
    "        #分别计算正方形内右上及左下区域内格子数及其等效区域数量，并做相应数学处理\n",
    "        loc1, cnt1 = (sideLength - w1) * h1, w0 * (h0 + 1)\n",
    "        loc2, cnt2 = (sideLength - h1) * w1, h0 * (w0 + 1)\n",
    "        if cnt1 < cnt2:\n",
    "            loc1, loc2 = loc2, loc1\n",
    "            cnt1, cnt2 = cnt2, cnt1\n",
    "        \n",
    "        # 若未超过等效区域多的格子数，直接分配后返回；否则再往另外一个区域分配\n",
    "        if maxOnes <= loc1 + loc2:\n",
    "            if maxOnes <= loc1:\n",
    "                return res + maxOnes * cnt1\n",
    "            else:\n",
    "                return res + loc1 * cnt1 + (maxOnes - loc1) * cnt2\n",
    "        # 若超过了2个区域的格子，则往两个格子分配后剩余的分配到右下角区域上（等效区域仅w0*h0个）\n",
    "        else:\n",
    "            return res + loc1 * cnt1 + loc2 * cnt2 + (maxOnes - loc1 - loc2) * w0 * h0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        L = []\n",
    "        for i in range(1, sideLength + 1):\n",
    "            for j in range(1, sideLength + 1):\n",
    "                L.append(((width - i) // sideLength + 1) * ((height - j) // sideLength + 1))\n",
    "        L.sort(reverse=True)\n",
    "        return sum(L[:maxOnes])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        return sum(sorted([((width-r-1)//sideLength+1)*((height-c-1)//sideLength+1) for r in range(sideLength) for c in range(sideLength)],reverse=True)[:maxOnes])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        return sum(sorted([((width-r-1)//sideLength+1)*((height-c-1)//sideLength+1) for r in range(sideLength) for c in range(sideLength)], reverse=True)[:maxOnes])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        counts = []\n",
    "        for i in range(sideLength):\n",
    "            for j in range(sideLength):\n",
    "                ones = ceil((height-i)/sideLength) * ceil((width-j)/sideLength)\n",
    "                counts.append(ones)\n",
    "        # print(counts)\n",
    "        return sum(sorted(counts, reverse=True)[:maxOnes])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "\n",
    "        a = []\n",
    "\n",
    "        wq, wr = divmod(width, sideLength)\n",
    "\n",
    "        hq, hr = divmod(height, sideLength)\n",
    "\n",
    "        for r in range(sideLength):\n",
    "\n",
    "            for c in range(sideLength):\n",
    "\n",
    "                ww = wq + 1 if r < wr else wq\n",
    "\n",
    "                hh = hq + 1 if c < hr else hq\n",
    "\n",
    "                a.append(ww * hh)\n",
    "\n",
    "        a.sort(reverse = True)\n",
    "\n",
    "        return sum(a[:maxOnes])\n",
    "\n",
    "# 作者：HanXin\n",
    "# 链接：https://leetcode.cn/problems/maximum-number-of-ones/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        cnt = []\n",
    "        for i in range(sideLength):\n",
    "            for j in range(sideLength):\n",
    "                x = (height - i - 1) // sideLength + 1\n",
    "                y = (width - j - 1) // sideLength + 1\n",
    "                cnt.append(x * y)\n",
    "        cnt.sort(reverse=True)\n",
    "        return sum(cnt[:maxOnes])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "\n",
    "        return sum(sorted([((width-r-1)//sideLength+1)*((height-c-1)//sideLength+1) for r in range(sideLength) for c in range(sideLength)],reverse=True)[:maxOnes])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        return sum(sorted([((width-r-1)//sideLength+1)*((height-c-1)//sideLength+1) for r in range(sideLength) for c in range(sideLength)],reverse=True)[:maxOnes])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        res = []\n",
    "        for i in range(sideLength):\n",
    "            for j in range(sideLength):\n",
    "                res.append(((width-i-1)//sideLength+1)*((height-j-1)//sideLength + 1))\n",
    "        res.sort(reverse=True)\n",
    "        return sum(res[:maxOnes])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\r\n",
    "        a = []\r\n",
    "        wq, wr = divmod(width, sideLength)\r\n",
    "        hq, hr = divmod(height, sideLength)\r\n",
    "        for r in range(sideLength):\r\n",
    "            for c in range(sideLength):\r\n",
    "                ww = wq + 1 if r < wr else wq\r\n",
    "                hh = hq + 1 if c < hr else hq\r\n",
    "                a.append(ww * hh)\r\n",
    "        a.sort(reverse = True)\r\n",
    "        return sum(a[:maxOnes])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        counts = []\n",
    "        for i in range(sideLength):\n",
    "            for j in range(sideLength):\n",
    "                ones = ceil((height-i)/sideLength) * ceil((width-j)/sideLength)\n",
    "                counts.append(ones)\n",
    "        print(counts)\n",
    "        return sum(sorted(counts, reverse=True)[:maxOnes])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:\n",
    "        cnt = []\n",
    "        for i in range(sideLength):\n",
    "            for j in range(sideLength):\n",
    "                x = (height - i - 1) // sideLength + 1\n",
    "                y = (width - j - 1) // sideLength + 1\n",
    "                cnt.append(x * y)\n",
    "        cnt.sort(reverse=True)\n",
    "        return sum(cnt[:maxOnes])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
